package leetCode;

/**
 * 快速排序
 */
public class FastSort {
    public static void main(String[] args) {
        int[] arr = {2, 5, 3, 22, 7, 9, 12};
        quick(arr,0,arr.length-1);
        for (int i:
             arr) {
            System.out.print(i+",");
        }
    }
    private static void quick(int[] arr, int left, int right) {

        int mid = (left + right) / 2;
        int midRes = arr[mid];
        int i = left;
        int j = right;

        for (; i < j; ) {
            while (i < mid && arr[i] < midRes) {
                i++;
            }
            if (i < mid) {
                arr[mid] = arr[i];
                mid = i;
            }
            while (j > mid && arr[j] > midRes) {
                j--;
            }
            if (j > mid) {
                arr[mid] = arr[j];
                mid = j;
            }
        }
        arr[mid] = midRes;
        if (mid - left > 1) {
            quick(arr, left, mid - 1);
        }
        if (right - mid > 1) {
            quick(arr, mid + 1, right);
        }

    }

}
